题目链接：QOJ Contest 3789 Problem A
题目要求动态维护一个访问顺序。每次交换相邻两个点后，要在整棵树中重新选择根，使得“后访问的点是先访问点的祖先”的点对数量尽量少。
如果固定一个根去计算答案，根一变，所有祖先关系都会变，似乎很难维护。更好处理的方向是反过来：固定一对点，去看它会对哪些根产生贡献。
对两个点 ，记 为删去 到 路径上的第一条边后，包含 的那个连通块。若当前选 为根，那么
这是因为当根在 这一侧时，从根走到 的路径一定经过 ；反过来，如果从根到 的路径经过 ，根也必然在删去第一条边后 所在的那一侧。
于是，排列中一个有序点对的贡献就不再是“对某个根加一”，而是“对某个连通块里的所有根加一”。这样就可以维护每个点作为根时的危险度，并支持对一块连通区域整体加减。
为了把这种连通块更新变成常规数据结构操作，先以 为根跑 DFS，得到每个点的子树区间。对于 ，如果 不是 的祖先，它就是 的子树；如果 是 的祖先，设 是从 走向 的下一个点，那么它就是全集去掉 的子树。也就是说，每次连通块更新都能表示成 DFS 序上的一个区间，或者一个区间的补集。用线段树维护每个根的当前危险度，即可支持区间加和全局最小值查询。
再看一次相邻交换。设本次交换的是
除了 这一对以外，任意两点的相对顺序都没有变化，所以答案数组的变化也只来自这一对。交换前， 在 前面，这一对贡献的是“ 是否为 的祖先”，也就是对 加一；交换后变成“ 是否为 的祖先”，也就是对 加一。因此操作时只要把前者减掉、后者加上：
每个 都能拆成常数个区间更新，所以一次交换只需要 。
剩下的是初始状态怎么建出来。设 表示点 在访问顺序中的位置。我们枚举后出现的点 ，统计它与所有更早出现的点会对哪些根产生贡献。
先假装无论根在哪里， 都会作为前面所有点的祖先，那么可以对所有根加上
这当然会多算。删去点 后，树会分成若干连通块。若根落在某个连通块 内，那么 内那些更早出现的点，从根到它们的路径不会经过 ，因此它们不该贡献。于是需要在这个连通块上减去
这些连通块仍然可以表示成子树或子树补集，所以最终也还是线段树上的区间加。
上式中的计数可以离线完成。按 从小到大扫描，用树状数组在 DFS 序上标记已经出现过的点。这样查询任意子树里已经出现过多少点，就是一次区间求和。得到所有需要减去的数量后，把每个点 对初始答案数组的贡献加入线段树即可。
建好初始线段树后，根的最小危险度就是线段树全局最小值；之后每次交换只做两次 更新，再输出全局最小值。
预处理、离线统计和建初值的复杂度为 ，每次交换复杂度为 。总时间复杂度为